import heapq


class Solution:
    def smallestRange(self, nums):
        heap = []
        re = []
        bestMax = nums[0][0]
        heapq.heappush(heap, (nums[0][0], 0, 0))
        for i in range(1, len(nums)):
            if nums[i][0] > bestMax:
                bestMax = nums[i][0]
            heapq.heappush(heap, (nums[i][0], i, 0))

        while True:
            nowMin = heapq.heappop(heap)
            if len(re) == 0:
                re = [nowMin[0], bestMax]
            elif re[1] - re[0] > bestMax - nowMin[0]:
                re = [nowMin[0], bestMax]
            k = nowMin[1]
            if nowMin[2] >= len(nums[k]) - 1:
                break
            if nums[k][nowMin[2] + 1] > bestMax:
                bestMax = nums[k][nowMin[2] + 1]
            heapq.heappush(heap, (nums[k][nowMin[2] + 1], k, nowMin[2] + 1))
        return re


if __name__ == '__main__':
    so = Solution()
    num = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]
    r = so.smallestRange(num)
    print(r)
